#include "stdafx.h"
#include "stdlib.h"
#include "time.h"

void heapifier(int *a, int i, int size)
{
	int done=0;
	int maxChild;
	while((i*2<size)&&(!done))
	{
		if (i*2==size)
			maxChild=i*2;
		else if(a[2*i]>a[2*i+1])
			maxChild=i*2;
		else maxChild=i*2+1;
	if (a[i]<a[maxChild])
	{
		int temp;
		temp=a[i];
		a[i]=a[maxChild];
		a[maxChild]=temp;
		i=maxChild;
	}
	else done=1;
	}
}
void HeapSort(int *a, int size)
{
	for(int i=size/2-1;i>=0;i--)
		heapifier(a,i,size);
	for(int i=size-1;i>=1;i--)
	{
		int temp;
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		heapifier(a,0,i-1);
	}
}
int main(int argc, char* args[])
{
	srand(time(NULL));
	const int size=10;
	int i,a[size];
	for(i=0;i<size;i++)
	{
		a[i]=rand()%100;
		printf("%d ",a[i]);
	};	
	printf("\n");
	HeapSort(a, size);
	for(i=0;i<size;i++)
		printf("%d ",a[i]);
}